package srcInterviewPrep;

public final class PowerModulo
{
    /**
     * Computes (x^y) % z, without using power function in O(log y) time.
     * Uses distributive property of modulo function: (a*b) % c = ((a%c) * (b%c)) % c
     * To compute (x^y) % z, first recursively calls itself compute to (x ^ (y/2)) % z,
     * then uses this value to compute (x ^ y) % z, by appropriately squaring, etc.
     * @param x
     * @param y
     * @param z
     * @return
     */
    public static int CalculatePowerModulo(int x, int y, int z)
    {
        int factor = x % z;
        if (y == 1)
        {
            return factor;
        }

        int value1 = CalculatePowerModulo(x, y/2, z);
        int value2;

        if (y % 2 == 0)
        {
            value2 = value1;
        }
        else
        {
            value2 = (factor * value1) % z;
        }

        return (value1 * value2) % z;
    }
}
